//https://leetcode.cn/problems/count-integers-in-intervals/description/?envType=daily-question&envId=2023-12-16



class CountIntervals {
static constexpr long long N = 1e9 + 1;

struct Node_t {
    int l, r;
    mutable int v;

    Node_t(const int &il, const int &ir, const int &iv) : l(il), r(ir), v(iv) {}

    bool operator<(const Node_t &o) const { return l < o.l; }
};

set<Node_t> odt;
long long m_sum = 0;

auto split(int x) {
    if (x > N) return odt.end();
    auto it = --odt.upper_bound(Node_t{x, 0, 0});
    if (it->l == x) return it;
    int l = it->l, r = it->r, v = it->v;
    odt.erase(it);
    odt.insert(Node_t(l, x - 1, v));
    return odt.insert(Node_t(x, r, v)).first;
}

void assign(int l, int r, int v) {
    auto itr = split(r + 1), itl = split(l);
    for (auto tmp_itl = itl; tmp_itl != itr; tmp_itl++) {
        m_sum -= (tmp_itl->r-tmp_itl->l+1)*tmp_itl->v;
    }
    odt.erase(itl, itr);
    odt.insert(Node_t(l, r, v));
    m_sum += (r-l+1)*v;
}

long long sum(int l, int r) {
    int sum = 0;
    auto itr = split(r + 1), itl = split(l);
    for (; itl != itr; ++itl) {
        sum += (itl->r-itl->l+1)*itl->v;
    }
    return sum;
}

public:
    CountIntervals() {
        odt.insert(Node_t(0, N + 1, 0));
    }
    
    void add(int left, int right) {
        assign(left, right, 1);
    }
    
    int count() {
        //return sum(0, n);
        return m_sum;

    }
};